package linkedlist;

public class ReorderList143 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // 用快慢指针将链表分成前后两段
        ListNode fast = head;
        ListNode slow = head;
        ListNode prevSlow = slow;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            prevSlow = slow;
            slow = slow.next;
        }

        // 如果有奇数个节点, 则fast非null, slow就是前半段的最后一个节点.
        // 如果有偶数个节点, 则fast为null, slow就是后半段的第一个节点, prevSlow就是前半段的最后一个节点.

        // 定位前半段最后一个节点
        ListNode firstHalfLast = (fast != null) ? slow : prevSlow;

        // 翻转后半段
        ListNode secondHalfFirst = reverse(firstHalfLast.next);

        // 将前半段最后一个节点的next置为null
        firstHalfLast.next = null;

        // 将后半段节点依次插入到前半段中
        ListNode firstHalfNode = head;
        ListNode secondHalfNode = secondHalfFirst;

        while (firstHalfNode != null && secondHalfNode != null) {
            ListNode firstHalfNodeNext = firstHalfNode.next;
            ListNode secondHalfNodeNext = secondHalfNode.next;

            secondHalfNode.next = firstHalfNodeNext;
            firstHalfNode.next = secondHalfNode;

            firstHalfNode = firstHalfNodeNext;
            secondHalfNode = secondHalfNodeNext;
        }
    }

    public ListNode reverse(ListNode start) {
        ListNode curr = start;
        ListNode prev = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
